package Stack;


import java.util.Stack;

/**
 * ClassName: 反转栈
 * Package: Stack
 *
 * @Author 马学兴
 * @Create 2024/2/4 10:47
 * @Version 1.0
 * Description:给你一个栈 stack，需要你把里面的元素进行反转，
 * 比如栈一开始时 1,2,3,4,5，反转后栈元素顺序变成 5,4,3,2,1。
 * 要求: 你不能使用数组，队列，栈等数据结构辅助，不过你可以用递归。
 */
public class Homework {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        stack = reverse(stack);//54321
      //  stack = reverse1(stack);//54321
        System.out.println(stack);//12345
    }
    //解法1
    //12345  54321
   public static Stack<Integer> reverse(Stack<Integer> stack){
        if (stack.isEmpty()||stack.size()==0){
            return stack;
        }
       int top= stack.pop();//先减少规模  12345  1234
       reverse(stack);//4321
       pushlast(stack,top);//加到栈底
       return stack;
   }
   //4321   54321
   public static Stack<Integer> pushlast(Stack<Integer> stack,int top){
        if (stack.isEmpty()){
            stack.push(top);
            return stack;
        }
        int tmp =stack.pop();//减少规模  4321  432
       pushlast(stack,top);//5432
       stack.push(tmp);
       return stack;

   }

    //解法2
    public static Stack<Integer> reverse1(Stack<Integer> stack){
        if (stack.size()==1||stack.isEmpty()){
            return stack;
        }
        int last=getLast(stack);//把最底的元素拿出来  2345
        stack=reverse1((stack));//5432
        stack.push(last);
        return stack;
    }
    //把最底的元素拿出来  2345
    public static int getLast(Stack<Integer> stack){
        if (stack.size()==1){
            return stack.pop();
        }
        //
        int tmp=stack.pop();//tmp=5  234
        int last=getLast(stack);//234  34
        stack.push(tmp);
        return last;


    }


}
